Advances in Computer Algebra by Carsten Schneider & Eugene Zima

Author:Carsten Schneider & Eugene Zima
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

For every fixed , denote by V(p) the set of all sequences with , i.e., the solution space of the recurrence equation encoded by p. This is a vector space of dimension . For any two operators there exists a unique monic polynomial such that V(r) is the vector space generated by all sequences with and , i.e., . We write .

Our problem shall be to decide, for a given monic polynomial , whether there exist such that . In principle, it is known how to do this. Singer [12] gives a general algorithm for the analogous problem for linear differential operators with rational function coefficients; the problem is further discussed in [6]. Because of their high cost, these algorithms are mainly of theoretical interest. For the special case of differential operators of order 3 or 4 (still with rational function coefficients), van Hoeij [15, 16] combines several observations to an algorithm which handle these cases efficiently. For the recurrence case, Cha [1] gives an algorithm for operators of order 3 with rational function coefficients.

Also the case of recurrence equations with constant coefficients has already been considered. Everest et al. give an algorithm [2] based on a structure theorem of Ritt [11]. This algorithm relies on Ge’s algorithm [4], which is efficient in theory but according to our experience rather costly in concrete examples. An alternative algorithm for the case of constant coefficients and arbitrary order was recently sketched by the second author [19]. This description, however, only considers the “generic case”. The present paper is a continuation of this work in which we give a complete algorithm which also handles “degenerate” cases. Our algorithm is efficient in the sense that it does not depend on Ge’s algorithm or on Gröbner basis computations, but it is inefficient in the sense that it requires a search that may take exponential time in the worst case.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.